﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using ParallelRuntimeLibrary.Internal;

namespace ParallelRuntimeLibrary.Collections
{
    /// <summary>
    /// Represend concurrent enabled first-in, first-out collection of object.
    /// </summary>
    /// <typeparam name="T">Specifies the type of elements in the queue</typeparam>
    public class ConcurrentQueue<T> : IConcurrentCollection<T>
    {
        private Segment mHead;
        private Segment mTail;
        private readonly int mSegmentSize;
        private bool mConcurrentMode;

        public bool ConcurrentMode
        {
            get
            {
                return mConcurrentMode;
            }
            set
            {
                mConcurrentMode = value;
            }
        }

        public int Count
        {
            get
            {
                Segment segment;
                Segment segment2;
                int num;
                int num2;

                GetHeadTailPositions(out segment, out segment2, out num, out num2);

                if (segment == segment2)
                    return ((num2 - num) + 1);
                else
                {
                    int num3 = mSegmentSize - num;
                    
                    for (Segment segment3 = segment.Next; segment3 != segment2; segment3 = segment3.Next)
                        num3 += mSegmentSize;

                    return num3 + (num2 + 1);
                }
            }
        }

        public bool IsEmpty
        {
            get
            {
                Segment head = mHead;
                if (head.IsEmpty)
                {
                    if (head.Next == null)
                        return true;
                    else
                    {
                        NativeMethod.SwitchToThread();

                        while (head.IsEmpty)
                        {
                            if (head.Next == null)
                                return true;

                            head = mHead;
                        }
                    }
                }
                return false;
            }
        }

        /*///////////////////////////////////////////////////////////////////////////////////////////////*/

        public ConcurrentQueue() : this(128, true, null)
        {
        }


        ///<summary></summary>
        /// <param name="segmentSize">The size of each Segment/piece the default is: 128. Choice it depend on your expeccted queue size.
        /// I recommend: 32, 64, 128, 256, 512, 1024</param>
        public ConcurrentQueue(int segmentSize) : this(segmentSize, true, null)
        {
        }


        public ConcurrentQueue(IEnumerable<T> collection) : this(128, true, collection)
        {
        }

        ///<summary></summary>
        /// <param name="segmentSize">The size of each Segment/piece the default is: 128. Choice it depend on your expeccted queue size.
        /// I recommend: 64, 128, 256, 512, 1024</param>
        public ConcurrentQueue(int segmentSize, bool concurrentEnabled, IEnumerable<T> collection)
        {
            //if (segmentSize < 32) segmentSize = 32;
            if (segmentSize > 2048) segmentSize = 2048;

            mConcurrentMode = concurrentEnabled;
            mSegmentSize = segmentSize;

            if (collection == null)
                mHead = mTail = new Segment(mSegmentSize);
            else
                InitializeFromCollection(collection);
        }



        private void InitializeFromCollection(IEnumerable<T> collection)
        {
            mHead = mTail = new Segment(mSegmentSize);
            int i = 0;

            foreach (T item in collection)
            {
                mTail.UnsafeAdd(item);
                i++;

                if (i >= mSegmentSize)
                {
                    mTail = mTail.UnsafeGrow();
                    i = 0;
                }
            }
        }

        /*///////////////////////////////////////////////////////////////////////////////////////////////*/

        private void GetHeadTailPositions(out Segment head, out Segment tail, out int headLow, out int tailHigh)
        {
            head = mHead;
            tail = mTail;
            headLow = head.Low;
            tailHigh = tail.High;

            while (((head != mHead) || (tail != mTail)) || ((headLow != head.Low) || (tailHigh != tail.High)))
            {
                NativeMethod.SwitchToThread();
                head = mHead;
                tail = mTail;
                headLow = head.Low;
                tailHigh = tail.High;
            }
        }

        public List<T> ToList()
        {
            Segment segment;
            Segment segment2;
            int num;
            int num2;

            GetHeadTailPositions(out segment, out segment2, out num, out num2);

            if (segment == segment2)
                return segment.ToList(num, num2);
            else
            {
                List<T> list = new List<T>(segment.ToList(num, mSegmentSize - 1));

                for (Segment segment3 = segment.Next; segment3 != segment2; segment3 = segment3.Next)
                    list.AddRange(segment3.ToList(0, mSegmentSize - 1));

                list.AddRange(segment2.ToList(0, num2));
                return list;
            }
        }

        public void Enqueue(T item)
        {
            if (mConcurrentMode)
            {
                while (true)
                {
                    if (mTail.TryEnqueue(item, ref mTail))
                        return;
                    else
                    {
                        if (mTail.TryEnqueue(item, ref mTail))
                            return;
                        else
                            NativeMethod.SwitchToThread();
                    }
                }
            }
            else
            {
                if (mTail.High == mSegmentSize - 1)
                    mTail = mTail.UnsafeGrow();
                
                mTail.UnsafeAdd(item);
            }
        }

        public bool Dequeue(out T result)
        {
            if (mConcurrentMode)
            {
                while (true)
                {
                    if (mHead.Low <= mHead.High)
                    {
                        if (mHead.TryDequeue(out result, ref mHead))
                            return true;
                    }
                    else if (IsEmpty)
                    {
                        result = default(T);
                        return false;
                    }
                }
            }
            else
            {
                if (mHead.UnsafeDequeue(out result, ref mHead))
                    return true;
                else
                {
                    result = default(T);
                    return false;
                }
            }
        }

        public bool Peek(out T result)
        {
            if (mConcurrentMode)
            {
                while (true)
                {
                    if (mHead.Low <= mHead.High)
                    {
                        if (mHead.TryPeek(out result))
                            return true;
                    }
                    else
                    {
                        result = default(T);
                        return false;
                    }
                }
            }
            else
                return mHead.UnsafePeek(out result);
        }

        /*////////////////////////////////////////////////////////////////////////////////////////////////*/

        #region IConcurrentCollection<T> Members

        public bool Add(T item)
        {
            Enqueue(item);
            return true;
        }

        public bool Remove(out T item)
        {
            return Dequeue(out item);
        }

        public T[] ToArray()
        {

            Segment segment;
            Segment segment2;
            int num;
            int num2;

            GetHeadTailPositions(out segment, out segment2, out num, out num2);

            if (segment == segment2)
                return segment.ToList(num, num2).ToArray();

            List<T> list = new List<T>(segment.ToList(num, mSegmentSize - 1));
            for (Segment segment3 = segment.Next; segment3 != segment2; segment3 = segment3.Next)
                list.AddRange(segment3.ToList(0, mSegmentSize - 1));

            list.AddRange(segment2.ToList(0, num2));
            return list.ToArray();
        }

        #endregion

        /*////////////////////////////////////////////////////////////////////////////////////////////////*/

        private sealed class Segment
        {
            internal readonly int mSegmentSize;
            internal readonly int mSegmentSizeL1;

            internal T[] mArray;
            private int mHigh;
            private int mLow;
            private ConcurrentQueue<T>.Segment mNext;
            private bool[] mState;

            /*///////////////////////////////////////////////////////////////////////////////////*/

            internal int High
            {
                get
                {
                    return  (mHigh > mSegmentSizeL1) ? mSegmentSizeL1 : mHigh ;
                }
            }

            internal bool IsEmpty
            {
                get
                {
                    return (mLow > mHigh);
                }
            }

            internal int Low
            {
                get
                {
                    return (mLow > mSegmentSize) ? mSegmentSize : mLow;
                }
            }

            internal ConcurrentQueue<T>.Segment Next
            {
                get
                {
                    return mNext;
                }
            }

            /*///////////////////////////////////////////////////////////////////////////////////*/

            internal Segment(int segmentSize)
            {
                mSegmentSize = segmentSize;
                mSegmentSizeL1 = segmentSize - 1;

                mArray = new T[segmentSize];
                mState = new bool[segmentSize];
                mNext = null;
                mLow = 0;
                mHigh = -1;
            }

            /*///////////////////////////////////////////////////////////////////////////////////*/

            internal bool TryEnqueue(T value, ref ConcurrentQueue<T>.Segment tail)
            {
                if (mHigh < mSegmentSizeL1)
                {
                    int index = mSegmentSize;

                    index = Interlocked.Increment(ref mHigh);
                    if (index <= mSegmentSizeL1)
                    {
                        mArray[index] = value;
                        mState[index] = true;
                    }

                    if (index < mSegmentSizeL1)
                        return true;

                    if (index == mSegmentSizeL1)
                    {
                        Grow(ref tail);
                        return true;
                    }
                }
                return false;
            }

            internal bool TryPeek(out T result)
            {
                int low = Low;
                if (low > High)
                {
                    result = default(T);
                    return false;
                }
                else
                {
                    result = mArray[low];
                    return true;
                }
            }

            internal bool TryDequeue(out T result, ref ConcurrentQueue<T>.Segment head)
            {
                int low = Low;

                for (int i = High; low <= i; i = High)
                {
                    if (Interlocked.CompareExchange(ref mLow, low + 1, low) == low)
                    {
                        while (mState[low] == false)
                        { Thread.SpinWait(1000000); }

                        result = mArray[low];

                        if (low >= mSegmentSizeL1)
                        {
                            while (mNext == null)
                            { Thread.SpinWait(100000); }

                            head = mNext;
                        }

                        return true;
                    }
                    NativeMethod.SwitchToThread();

                    low = Low;
                }

                result = default(T);
                return false;
            }

            /*///////////////////////////////////////////////////////////////////////////////////*/

            internal bool UnsafePeek(out T result)
            {
                int low = mLow;
                if (Low > mHigh)
                {
                    result = default(T);
                    return false;
                }
                else
                {
                    result = mArray[low];
                    return true;
                }
            }

            internal bool UnsafeDequeue(out T result, ref ConcurrentQueue<T>.Segment head)
            {
                if (mLow <= mHigh)
                {
                    int low = mLow;
                    result = mArray[mLow++];

                    if (low >= mSegmentSizeL1)
                        head = mNext;

                    return true;
                }

                result = default(T);
                return false;
            }

            internal void UnsafeAdd(T value)
            {
                mHigh++;
                mArray[mHigh] = value;
                mState[mHigh] = true;
            }

            internal ConcurrentQueue<T>.Segment UnsafeGrow()
            {
                ConcurrentQueue<T>.Segment segment = new ConcurrentQueue<T>.Segment(mSegmentSize);
                mNext = segment;
                return segment;
            }

            /*///////////////////////////////////////////////////////////////////////////////////*/

            internal void Grow(ref ConcurrentQueue<T>.Segment tail)
            {
                this.mNext = new ConcurrentQueue<T>.Segment(mSegmentSize);
                tail = this.mNext;
            }

            internal List<T> ToList(int start, int end)
            {
                List<T> list = new List<T>();
                for (int i = start; i <= end; i++)
                {
                    while (this.mState[i] == false)
                        NativeMethod.SwitchToThread();

                    list.Add(this.mArray[i]);
                }
                return list;
            }

        }

        
    }

    
}
